package com.demo.java.OD201_250.OD204;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【选座位】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145905712
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String input = sc.nextLine().trim();
            if (input.isEmpty()) {
                continue;
            }
            int n = Integer.parseInt(input);  // 总座位数
            input = sc.nextLine().trim();
            if (input.isEmpty()) {
                continue;
            }
            String[] s = input.substring(1, input.length() - 1).split(",");  // 操作列表
            List<Integer> seats = Arrays.stream(s).map(Integer::parseInt).collect(
                    Collectors.toList());  // 转换为整数列表
            int ans = getMaxSocialDistance(seats, n);  // 获取结果
            System.out.println(ans);  // 输出结果
        }
    }

    private static int getMaxSocialDistance(List<Integer> seats, int n) {
        TreeSet<Integer> seated = new TreeSet<>();  // 用于记录已占用的座位
        for (int i = 0; i < seats.size(); i++) {
            int op = seats.get(i);  // 当前操作
            if (op > 0) {  // 占用座位
                if (seated.size() == 0) {
                    if (i == seats.size() - 1) {
                        return 0;
                    }
                    seated.add(0);  // 初始化座位
                } else if (seated.size() == 1) {
                    seated.add(n - 1);  // 如果只有一个已占用座位，选择最后一个座位
                    if (i == seats.size() - 1) {
                        return n - 1;  // 如果是最后一次操作，返回结果
                    }
                } else if (seated.size() > 1 && seated.size() < n) {
                    int[] ints = new int[seated.size()];
                    int count = 0;
                    for (Integer num : seated) {
                        ints[count++] = num;
                    }
                    int maxLen = 0;
                    int start = 0;
                    // 计算各已占用座位之间的最大空隙
                    for (int j = 0; j < ints.length - 1; j++) {
                        int len = ints[j + 1] - ints[j];
                        if (len / 2 > maxLen) {
                            maxLen = len / 2;
                            start = ints[j];
                        }
                    }
                    seated.add(start + maxLen);  // 分配最远座位
                    if (i == seats.size() - 1) {
                        return start + maxLen;  // 返回结果
                    }
                } else {
                    return -1;  // 如果无法分配座位，则返回 -1
                }
            } else {  // 释放座位
                seated.remove(-op);
            }
        }
        return 0;  // 默认返回0
    }
}